package net.projecteuler.util;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

public class FactorUtil {	
	public static int[][] primeFactorization(int value){
		if(value < 2) return null;
		
		List<Integer> factorList = new ArrayList<Integer>();
		List<Integer> powerList = new ArrayList<Integer>();
		
		int primeIdx = 0;
		while(true){
			int factor = PrimeUtil.PrimeList.get(primeIdx);
			int power = 0;
			
			if(factor > value)
				break;
			
			while(true){
				if(value % factor == 0){
					power++;
					value /= factor;
				} else {
					break;
				}
			}
			
			if(power > 0){
				factorList.add(factor);
				powerList.add(power);
			}
			
			primeIdx++;
		}
		
		int[][] factorization = new int[factorList.size()][2];
		for(int i = 0; i < factorList.size(); i++){
			factorization[i][0] = factorList.get(i);
			factorization[i][1] = powerList.get(i);
		}
		
		return factorization;
	}
	
	public static int[] divisors(int value){
		if(value < 2) return null;
		
		int[][] factors = primeFactorization(value);
		int caseCnt = 1;
		for(int i = 0; i < factors.length; i++)
			caseCnt *= (factors[i][1] + 1);
		
		// list of divisors without eliminating duplicates. 
		List<Integer> divisorTemp = new ArrayList<Integer>(caseCnt);
		divisorRecurParam param = new divisorRecurParam();
		param.factors = factors;
		param.factorIdx = 0;
		param.offset = 1;
		param.divisorTemp = divisorTemp;
		divisorRecur(param);
		
		// sort...
		Comparator<Integer> comparator = new Comparator<Integer>() {
			@Override
			public int compare(Integer o1, Integer o2) {
				if(o1 > o2)
					return 1;
				else if(o1 < o2)
					return -1;
				return 0;
			}
		};
		Collections.sort(divisorTemp, comparator);
		
		// elim duplicates.
		int nDivisors = 1;
		for(int i = 1; i < divisorTemp.size(); i++)
			if(divisorTemp.get(i) != divisorTemp.get(i - 1))
				nDivisors++;
		
		int idxTemp = 0;
		int[] result = new int[nDivisors];
		result[0] = 1;
		for(int i = 1; i < divisorTemp.size(); i++)
			if(divisorTemp.get(i) != divisorTemp.get(i - 1))
				result[++idxTemp] = divisorTemp.get(i);
		
		return result;
	}
	
	public static void divisorRecur(divisorRecurParam param){
		if(param.factorIdx == param.factors.length - 1){
			int factor = param.factors[param.factorIdx][0];
			int power = param.factors[param.factorIdx][1];
			int offset = param.offset;
			for(int i = 0; i <= power; i++){
				param.divisorTemp.add(offset);
				if(i != power)
					offset *= factor;
			}
		} else {
			divisorRecurParam paramNext = new divisorRecurParam();
			paramNext.factors = param.factors;
			paramNext.factorIdx = param.factorIdx + 1;
			paramNext.divisorTemp = param.divisorTemp;
			paramNext.offset = param.offset;
			int factor = param.factors[param.factorIdx][0];
			int power = param.factors[param.factorIdx][1];
			for(int i = 0; i <= power; i++){
				divisorRecur(paramNext);
				if(i != power)
					paramNext.offset *= factor;
			}
		}
			
	}
	
	private static class divisorRecurParam{
		public int[][] factors;
		public int factorIdx;
		public int offset;
		public List<Integer> divisorTemp;
	}
	
	public static int totientPhi(int n){
		if(n < 1) return 0;
		if(n == 1) return 1;
		
		int val = n;
		int[][] factors = primeFactorization(n);
		for(int i = 0; i < factors.length; i++){
			val /= factors[i][0];
			val *= factors[i][0] - 1;
		}
		
		return val;
	}
	
	public static boolean isCoprimeEuclidean(int a, int b){
		return gcdEuclidean(a, b) == 1;
	}
	
	public static int gcdEuclidean(int a, int b){
		if(a < 1 || b < 1)
			return 0;
		else if(a == b)
			return a;
		else {
			int t = 0;
			
			if(b > a){
				t = a;
				a = b;
				b = t;
			} else {
				t = b;
			}
			
			while(t > 0){
				t = a % b;
				a = b;
				b = t;
			}
			
			return a;
		}
	}
}
